적대적 탐색과 제약 만족

제 3강에 오신 것을 환영합니다: 인공지능 개념 (PolyU COMP5511). 이번 강의에서는 단일 에이전트 경로 탐색에서 적대적 탐색으로 전환하며, 이는 에이전트가 경쟁적인 다중 에이전트 환경에서 작동하는 개념입니다. 또한 제약 만족 문제(CSP)를 소개합니다. 이는 경로 대신 특정 제약 조건을 만족하는 상태를 찾는 것을 목표로 하는 패러다임입니다.

핵심 개념

• 적대적 탐색: 지능적인 상대에 맞서 합리적인 결정을 내리기 위한 미니맥스 및 알파-베타 가지치기 와 같은 알고리즘에 초점을 맞춥니다.
• 몬테카를로 트리 탐색(MCTS): 확률적 의사 결정을 탐구하며, 알파고와 같은 현대 게임 AI의 핵심 기술로 자리잡았습니다.
• 제약 만족: 변수, 도메인, 제약 조건을 사용하여 문제를 모델링하며, 백트래킹 및 국소 탐색와 같은 현대 게임 AI의 핵심 기술로 자리잡았습니다.

복잡도 분석

적대적 환경에서 탐색 공간의 복잡도는 흔히 게임의 분기 계수 $b$ 와 깊이 $d$로 정의되며, 계산 비용은 다음과 같습니다: $$O(b^d)$$ 이러한 지수적 증가로 인해 알파-베타 가지치기와 같은 효율적인 가지치기 전략이 필요합니다.